Now that we've outlined our learning objectives, let's begin by exploring the fundamental problem we aim to solve. Imagine you need to connect a set of locations—be it cities with fiber optic cables, houses to a power grid, or servers in a network—using the least amount of material or cost.

  • The goal is to create a network that connects every single location (vertex).
  • The network must have no redundant loops or cycles (it's a tree).
  • It must achieve this with the lowest possible total cost (minimum sum of edge weights).
  • This problem is solved by finding a Minimum Spanning Tree (MST).
  • An MST is a special subgraph providing a backbone connection for a larger network, ensuring full connectivity at the minimum possible expense.

Minimum Spanning Tree (MST)

For a given connected, weighted, undirected graph $G = (V, E)$, a Minimum Spanning Tree is a subgraph that connects all vertices in $V$ together with $V-1$ edges, contains no cycles, and has the minimum possible sum of edge weights $w(u, v)$.